def partition(arr,left,right):
    # 标准值为arr[left]
    idx=left+1
    for i in range(left+1,right+1):
        if arr[i]<=arr[left]:
            arr[i],arr[idx]=arr[idx],arr[i]
            idx+=1
    # 将前半部分最后一个和基准值交换
    arr[left],arr[idx-1]=arr[idx-1],arr[left]
    return idx-1

def quick_sort(arr,left,right):
    if left<right:
        mid=partition(arr,left,right)
        # 将arr分为三部分
        quick_sort(arr,left,mid-1)
        quick_sort(arr,mid+1,right)


a=[2,3,5,7,4,1]
quick_sort(a,0,len(a)-1)
print(a)

# def partition(arr,left,right):
#     # 以arr[left]为基准数
#     i,j=left,right
#     while i<j:
#         # 从右边找首个小于基准数的元素
#         while i<j and arr[j]>=arr[left]:
#             j-=1
#         # 从左边找首个大于基准数的元素
#         while i<j and arr[i]<=arr[left]:
#             i+=1
#         arr[i],arr[j]=arr[j],arr[i]
#     arr[i],arr[left]=arr[left],arr[i]
#     return i
#
# def quick_sort(nums, left, right):
#     """快速排序"""
#     # 子数组长度为 1 时终止递归
#     if left >= right:
#         return
#     # 哨兵划分
#     pivot = partition(nums, left, right)
#     # 递归左子数组、右子数组
#     quick_sort(nums, left, pivot - 1)
#     quick_sort(nums, pivot + 1, right)

